package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class LeetCode_day9 {
	
	/**
	 * Method 1: all anagrams have the same sorted word.
	 * 			which means, when sort them, it results in the same form
	 * @param strs
	 */
	public static void anagrams(String[] strs){
		HashMap<String, List<Integer>> hm = new HashMap<String, List<Integer>>();
		
		int ind = 0;
		for(String s : strs){
			char[] c = s.toCharArray();
			Arrays.sort(c);
			String str = c.toString().intern();
			if(hm.containsKey(str)) hm.get(str).add(ind);
			else{
				List<Integer> list = new ArrayList<Integer>();
				list.add(ind);
				hm.put(str, list);
			}
			ind++;
		}
		
		for(String s : hm.keySet()){
			for(Integer i : hm.get(s))
				System.out.println(strs[i]+", ");
			System.out.println();
		}
	}
	
	/**
	 * When using the traditional method, it will have high complexity
	 * When we do 2^1000, then:
	 * 2^1000 = (2^500) * (2^500)
	 * 2^500 = 2^125 * 2^125
	 * 
	 * A simple divide-and-conquer
	 * 
	 * @param x
	 * @param n
	 * @return
	 */
	public static double pow(double x, int n){
		if(n == 0) return 1.0;
		double half = pow(x, n/2);
		if(n % 2 == 0) return half * half;
		else if(n > 0) return half * half * x;
		else return half * half / x;//n < 0
	}
	
	/**
	 * Optimizations:
	 * we don't need to store the whole board in every step
	 * we only need to store the queen's position in every step
	 * @param n
	 */
	public static void nQueensI(int n){
		char[][] board = new char[n][n];
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j++)
				board[i][j] = 'x';
		List<char[][]> results = new ArrayList<char[][]>();
		nQueensDFSI(board, 0, results);
		
		for(char[][] result : results){
			System.out.println("Result :");
			printBoard(result);
			System.out.println();
		}
	}
	
	public static void printBoard(char[][] board){
		int n = board.length;
		for(int i = 0 ; i < n ; i++){
			for(int j = 0 ; j < n ; j++)
				System.out.print(board[i][j]+" ");
			System.out.println();
		}
	}
	public static void nQueensDFSI(char[][] board, int step , List<char[][]> results){
		
		if(step == board.length) {
			results.add(board);
			return;
		}
		for(int i = 0 ; i < board.length ; i++){
			char[][] newboard = new char[board.length][board.length];
			for(int j = 0 ; j < board.length ; j++)
				newboard[j] = Arrays.copyOf(board[j], board.length);
			if(newboard[i][step] == 'x'){
				//remove all possible trap
				addNewQueen(newboard, i, step);
				//printBoard(newboard);
				nQueensDFSI(newboard, step+1, results);
			}
		}
	}
	
	public static void addNewQueen(char[][] board, int x, int y){
		board[x][y] = 'Q';
		for(int i = 0 ; i < board.length ; i++){
			if(i != x)  board[i][y] = '.';//vertical
			if(i != y)  board[x][i] = '.';//horizontal
		}
		
		int m = x-1, n = y-1;
		//left upper
		while(m >= 0 && n >= 0){
			board[m][n] = '.';
			m--; n--;
		}
		
		m = x-1; n= y+1;
		//left down
		while(m >= 0 && n < board.length){
			board[m][n] = '.';
			m--; n++;
		}
		
		m = x+1; n= y-1;
		//right upper
		while(n >= 0 && m < board.length){
			board[m][n] = '.';
			m++; n--;
		}
		
		m = x+1; n= y+1;
		//right down
		while(m < board.length && n < board.length){
			board[m][n] = '.';
			m++; n++;
		}
	}
	
	/**
	 * 把棋盘存储为一个N维数组a[N]，数组中第i个元素的值代表第i行的皇后位置，
	 * 这样便可以把问题的空间规模压缩为一维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，
	 * 且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。
	 * 至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等，
	 * 即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。
	 * 
	 * 
	 * Another method:
	 * 拿一个整数来代表棋盘的一列，用这个整数中的各个二进制位保存这一列里某个格子是不是能放子。
	 * 然后用三个变量，分别保存之前各列中的皇后能够横吃的格子、能够上斜吃的格子、能够下斜吃的格子，
	 * 看看合起来是不是还有空位，没有的话就回溯，有的话就把子放下去，更新上面三个变量，
	 * 继续走下去，他那个 row / ld / rd 就是干这个的。对照规则很容易就能想通了。 
	 * @param n
	 */
	public static void nQueensOptimization(int n){
		List<int[]> results = new ArrayList<int[]>();
		int[] positions = new int[n];
		Arrays.fill(positions, -1);
		nQueensDFSOpt(positions, 0, results);
	}
	
	public static void nQueensDFSOpt(int[] positions, int step, List<int[]> results){
		if(step == positions.length){
			results.add(positions);
			return;
		}
		for(int i = 0 ; i < positions.length ; i++){
			if(addNewQueenValid(positions, step, i)){
				int[] newpos = Arrays.copyOf(positions, positions.length);
				newpos[step] = i;
				nQueensDFSOpt(newpos, step+1, results);
			}
		}
	}
	
	public static boolean addNewQueenValid(int[] positions, int step, int val){
		for(int i = 0 ; i < step ; i++)
			if(positions[i] == val|| Math.abs(i-step) == Math.abs(val - positions[i])) return false;
		return true;
	}
	
	/**
	 * Find the contiguous subarray within an array (containing at least one number) 
	 * which has the largest sum.
	 * For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
	 * the contiguous subarray [4,−1,2,1] has the largest sum = 6.
	 * @param a
	 */
	public static void maximumSubarray(int[] a){
		if(a == null) return;
		int[] maxSum = new int[a.length*a.length];
		Arrays.fill(maxSum, Integer.MIN_VALUE);
		for(int i = 0 ; i < a.length ; i++) maxSum[i*a.length+i] = a[i];
		
		for(int len = 2 ; len <= a.length ; len++){
			for(int i = 0 ; i <= a.length - len ; i++){
				//int opt1 = a[i]>0 ? maxSum[i+1][i+len-1]+a[i] : maxSum[i+1][i+len-1];
				//int opt2 = a[i+len-1]>0 ? maxSum[i][i+len-2]+a[i+len-1]:maxSum[i][i+len-2];
				maxSum[i*a.length+i+len-1] = maxSum[i*a.length+i+len-2]+a[i+len-1];
			}
		}
		Arrays.sort(maxSum);
		System.out.println("Max sum is:" + maxSum[maxSum.length-1]);
	}
	
	/**
	 * Given a matrix of m x n elements (m rows, n columns), 
	 * return all elements of the matrix in spiral order.
	 * For example,
	 * Given the following matrix:
	 * [
	 * 	[ 1, 2, 3 ],
	 * 	[ 4, 5, 6 ],
	 * 	[ 7, 8, 9 ]
	 * ]
	 * You should return [1,2,3,6,9,8,7,4,5].
	 * Analysis:
	 * 1,2,3,6,9,8,7,4 is layer 1
	 * 5 is layer 2
	 * @param matrix
	 */
	public static void spiralMatrix(int[][] matrix){
		if(matrix == null) return;
		int m = matrix.length, n = matrix[0].length;
		int[] result = new int[m*n]; int count = 0;
		int layer = Math.min(m, n) / 2;
		for(int k = 0 ; k <= layer ; k++){
			//upper
			for(int i = k ; i < n-k ; i++)
				if(count < result.length)//notice, without this, it will exceeds
					result[count++] = matrix[k][i];
			//right
			for(int i = k+1 ; i < m-k-1 ; i++)
				if(count < result.length)
					result[count++] = matrix[i][n-k-1];
			//down
			for(int i = n-k-1 ; i >= k ; i--)
				if(count < result.length)
					result[count++] = matrix[m-k-1][i];
			//left
			for(int i = m-k-2 ; i >= k+1 ; i--)
				if(count < result.length)
					result[count++] = matrix[i][k];
		}
		
		System.out.println();
		for(int i : result)
			System.out.print(i+ " ");
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		nQueensI(4);
		maximumSubarray(new int[]{-2,1,-3,4,-1,2,1,-5,4});
		int[][] matrix = new int[3][4];
		matrix[0] = new int[]{1,2,3,4};
		matrix[1] = new int[]{5,6,7,8};
		matrix[2] = new int[]{9,10,11,12};
		spiralMatrix(matrix);
		System.out.println();
	}

}
